package com.zhanghp.class037;

import com.zhanghp.common.TreeNode;

/**
 * 验证平衡二叉树<br/>
 * 测试链接 : https://leetcode.cn/problems/balanced-binary-tree/
 *
 * @author zhanghp
 * @since 2024/4/19 16:39
 */
public class Code04_BalancedBinaryTree {

    static class Solution {
        public boolean isBalanced(TreeNode root) {
            // balance是全局变量，所有调用过程共享
            // 所以每次判断开始时，设置为true
            isBalance = true;
            f(root);
            return isBalance;
        }

        public boolean isBalance;

        public int f(TreeNode node){
            if (!isBalance || node == null) {
                return 0;
            }
            int l = f(node.left);
            int r = f(node.right);
            if (Math.abs(l-r) > 1) {
                isBalance = false;
            }
            // +1:本节点
            // max:用于和另一个孩子比较
            // 上面判断已经判断是否相差1，是否处理isBalance
            // 所以这里直接返回最大值就行，让上一层继续判断
            return Math.max(l, r) + 1;
        }

    }
}
